package cn.bellychang.leetcode.question102;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ChangLiang
 * @date 2021/2/7
 */
public class Solution {

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root == null) {
            return list;
        }

        List<TreeNode> currentListNode = new ArrayList();
        currentListNode.add(root);
        // loop invariant: 这一层遍历完了 获取下一层的节点
        while (true) {
            List<Integer> levelList = new ArrayList<>();
            for (TreeNode treeNode : currentListNode) {
                levelList.add(treeNode.val);
            }
            list.add(levelList);
            currentListNode = getLowerLevelNodeList(currentListNode);
            if (currentListNode == null || currentListNode.size()==0) {
                break;
            }
        }
        return list;
    }

    private List<TreeNode> getLowerLevelNodeList(List<TreeNode> list) {
        List<TreeNode> lowerLeverNodeList = new ArrayList<>();
        for (TreeNode treeNode : list) {
            if (!isLastLevel(treeNode)) {
                if (treeNode.left != null) {
                    lowerLeverNodeList.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    lowerLeverNodeList.add(treeNode.right);
                }
            }
        }
        return lowerLeverNodeList;
    }

    private boolean isLastLevel(TreeNode treeNode) {

        if (treeNode == null) {
            return true;
        }

        if (treeNode.left == null && treeNode.right == null) {
            return true;
        }

        return false;
    }
}
